package com.itheima.leetcode.od.b.bf;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;

/**
 * (B卷,200分)- 区间交集（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 给定一组闭区间，其中部分区间存在交集。
 * <p>
 * 任意两个给定区间的交集，称为公共区间(如:[1,2],[2,3]的公共区间为[2,2]，[3,5],[3,6]的公共区间为[3,5])。
 * <p>
 * 公共区间之间若存在交集，则需要合并(如:[1,3],[3,5]区间存在交集[3,3]，需合并为[1,5])。
 * <p>
 * 按升序排列输出合并后的区间列表。
 * <p>
 * 输入描述
 * <p>
 * 一组区间列表，
 * <p>
 * 区间数为 N: 0<=N<=1000;
 * <p>
 * 区间元素为 X: -10000<=X<=10000。
 * <p>
 * 输出描述
 * <p>
 * 升序排列的合并区间列表
 * <p>
 * 备注
 * 区间元素均为数字，不考虑字母、符号等异常输入。
 * 单个区间认定为无公共区间。
 * <p>
 * 用例
 * <p>
 * 输入	4
 * 0 3
 * 1 3
 * 3 5
 * 3 6
 * 输出	1 5
 * 说明
 * [0,3]和[1,3]的公共区间为[1,3]，
 * <p>
 * [0,3]和[3,5]的公共区间为[3,3]，
 * <p>
 * [0,3]和[3,6]的公共区间为[3,3]，
 * <p>
 * [1,3]和[3,5]的公共区间为[3,3]，
 * <p>
 * [1,3]和[3,6]的公共区间为[3,3]，
 * <p>
 * [3,5]和[3,6]的公共区间为[3,5]，
 * <p>
 * 公共区间列表为[[1,3],[3,3],[3,5]]；
 * <p>
 * [1,3],[3,3],[3,5]存在交集，须合并为[1,5]。
 * <p>
 * 输入
 * 4
 * 0 3
 * 1 4
 * 4 7
 * 5 8
 * <p>
 * 输出	1 3
 * 4 4
 * 5 7
 * 说明	无
 * 输入
 * 2
 * 1 2
 * 3 4
 * <p>
 * 输出	None
 * 说明	[1,2]和[3,4]无交集
 * <p>
 * 题目解析
 * <p>
 * 本题主要考察：区间交集求解、以及区间合并。
 * <p>
 * 首先，我们要求解输入的多个区间中，任意两个区间的交集（公共区间）。
 * <p>
 * 然后，将这些公共区间进行合并后打印。
 * <p>
 * 两个区间的交集求解思路如下：
 * <p>
 * 将两个区间按照开始位置进行升序，假设排序后，两个区间顺序是：[[s1, e1]，[s2, e2]]
 * <p>
 * 那么必然 s1 <= s2，因此如果存在交集的话，即e1 >= s2
 * <p>
 * 则交集的左边界必然是s2，而交集的右边界取值Math.min(e1, e2)
 * <p>
 * 区间合并的逻辑可以参考：华为机试 - 路灯照明问题_伏城之外的博客-CSDN博客
 */
public class IntervalsIntersection {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[][] ranges = new int[n][2];
        for (int i = 0; i < n; i++) {
            ranges[i][0] = sc.nextInt();
            ranges[i][1] = sc.nextInt();
        }*/

        int n = 4;
        int[][] ranges = Arrays.stream("0 3\n1 3\n3 5\n3 6".split("\n"))
                .map(s -> Arrays.stream(s.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        System.out.println(getResult(n, ranges));
    }

    public static String getResult(int n, int[][] ranges) {
        // 区间按照开始位置升序
        Arrays.sort(ranges, (a, b) -> a[0] - b[0]);

        // combine用于保存交集
        ArrayList<ArrayList<Integer>> combine = new ArrayList<>();

        // 求任意两个区间之间的交集
        for (int i = 0; i < n; i++) {
            int s1 = ranges[i][0];
            int e1 = ranges[i][1];
            for (int j = i + 1; j < n; j++) {
                int s2 = ranges[j][0];
                int e2 = ranges[j][1];
                if (s2 <= e1) {
                    int[] tempArr = new int[]{s2, Math.min(e1, e2)};
                    combine.add(Arrays.stream(tempArr)
                            .boxed()
                            .collect(Collectors.toCollection(ArrayList::new)));
                } else {
                    // 由于ranges已经升序，因此如果ranges[i]和ranges[j]没有交集的话，则也不可能和ranges[j+1]区间有交集
                    break;
                }
            }
        }

        if (combine.size() == 0) {
            return "None";
        }

        // 提前多级排序（多级排序类比 sql 的多条件 order by）
        combine.sort((a, b) -> a.get(1) - b.get(1));

        // 合并公共区间
        // 20250709-while循环合并版本
        outer:
        while (true) {

            for (int i = combine.size() - 1; i >= 0; i--) {

                for (int j = i - 1; j >= 0; j++) {
                    ArrayList<Integer> cur = combine.get(i);
                    ArrayList<Integer> pre = combine.get(j);

                    if (canUnion(pre, cur)) {
                        pre.set(1, Math.max(pre.get(1), cur.get(1)));
                        combine.remove(i);
                        continue outer;
                    } else {
                        break; // 记得剪枝（combine已经升序排序，因此如果pre和cur没有交集的话，则也不可能后续的区间有交集）
                    }
                }
            }
            break;
        }

        return combine.toString();
    }

    public static boolean canUnion(ArrayList<Integer> pre, ArrayList<Integer> cur) {
        return pre.get(1) >= cur.get(0) ? true : false; // 已经提前排序combine了，pre左边界永远 <= cur左边界
    }
}